package com.fanco.learn_datastruct_leetcode.leetcode;
import java.util.*;
/**
 * 给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词指字母相同，但排列不同的字符串。
 *
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 *
 * @author Fanco
 */
public class Day24 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String [] testStrs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        System.out.println(solution.groupAnagrams(testStrs));
    }
    private static class Solution {
        /**
         * 字母异位词 表示 字母一样，只是组合的顺序不一样。
         * 对某一个字母都进行重新排序，取排序后的 字符串为 key, 原来的字符串 为 value中的一个。
         * @param strs
         * @return
         */
        public List<List<String>> groupAnagrams(String[] strs) {

            Map<String, List<String>> map = new HashMap<>();

            for (String str : strs) {
                char[] chars = str.toCharArray();
                Arrays.sort(chars);
                String key = Arrays.toString(chars);

                if (map.containsKey(key)) {
                    map.get(key).add(str);
                } else {
                    List<String> list = new ArrayList<>();
                    list.add(str);
                    map.put(key, list);
                }
            }

            List<List<String>> res = new ArrayList<>();
            map.values().forEach(e -> {
                res.add(e);
            });
            return res;

        }
    }
}
